// https://leetcode.cn/problems/unique-paths/submissions/498278958/

function uniquePaths(m: number, n: number): number {
    // 1.定义状态dpd 的二维数组
    let dp:number[][] = Array.from({length: m}, ()=>{
        return Array(n).fill(0);
    }) 
    // 2. 设置初始值
    /**
     * [
     *  [1,1,1,1,1],
     *  [1,0,0,0,0],
     *  [1,0,0,0,0],
     * ]
     */
    // 遍历行，让第一列都为 1
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1
    }
    // 遍历列，让第一行都为1
    for (let j = 0; j < n; j++) {
        dp[0][j] = 1
    }
    console.log(dp)
    // 3.动态规划方程
    for(let i = 1; i < m; i++) {
        for(let j = 1; j < n; j++){
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        }
    }

    // 4. 返回的结果
    return dp[m -1][n - 1];
};

console.log(uniquePaths(3,7))

export {}